#include "CampusGraph.h"
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <limits.h>
#include <queue>

using namespace std;

bool CampusGraph::loadFromFile(const string &filename) {
  ifstream file(filename);
  if (!file.is_open()) {
    cout << "无法打开文件！" << endl;
    return false;
  }

  string line;
  while (getline(file, line)) {
    if (line.empty() || line.substr(0, 2) == "//")
      continue;

    if (line.substr(0, 2) == "n=") {
      numVertices = stoi(line.substr(2));
      adjacencyMatrix.resize(
          numVertices, vector<int>(numVertices, numeric_limits<int>::max()));
      for (int i = 0; i < numVertices; i++) {
        adjacencyMatrix[i][i] = 0;
      }
    } else if (line.substr(0, 2) == "v=") {
      istringstream iss(line.substr(2));
      string vertex;
      int index = 0;
      while (iss >> vertex) {
        if (index >= numVertices) {
            cout << "错误：景点数量超过了预定义的数量 " << numVertices << "!" << endl;
            return false;
        }
        vertices.push_back(vertex);
        vertexIndex[vertex] = index++;
      }
    } else if (line[0] == '(') {
      line = line.substr(1, line.length() - 2);
      istringstream iss(line);
      string v1, v2;
      int weight;
      iss >> v1 >> v2 >> weight;

      if (vertexIndex.find(v1) == vertexIndex.end()) {
        cout << "错误：景点 " << v1 << " 不存在!" << endl;
        return false;
      }
      if (vertexIndex.find(v2) == vertexIndex.end()) {
        cout << "错误：景点 " << v2 << " 不存在!" << endl;
        return false;
      }
      int i = vertexIndex[v1];
      int j = vertexIndex[v2];
      adjacencyMatrix[i][j] = weight;
      adjacencyMatrix[j][i] = weight; // 无向图
    }
  }

  initializeFloyd();
  floydWarshall();
  return true;
}

void CampusGraph::showVertices() {
  cout << "\n=== 景点列表 ===\n\n";
  for (int i = 0; i < vertices.size(); i++) {
    cout << i + 1 << "." << vertices[i] << ((i + 1) % 3 ? "  " : "\n");
  }
}

void CampusGraph::initializeFloyd() {
  nextVertex.resize(numVertices, vector<int>(numVertices, -1));
  for (int i = 0; i < numVertices; i++) {
    for (int j = 0; j < numVertices; j++) {
      if (adjacencyMatrix[i][j] != numeric_limits<int>::max()) {
        nextVertex[i][j] = j;
      }
    }
  }
}

void CampusGraph::floydWarshall() {
  for (int k = 0; k < numVertices; k++) {
    for (int i = 0; i < numVertices; i++) {
      for (int j = 0; j < numVertices; j++) {
        if (adjacencyMatrix[i][k] != numeric_limits<int>::max() &&
            adjacencyMatrix[k][j] != numeric_limits<int>::max()) {
          int newDist = adjacencyMatrix[i][k] + adjacencyMatrix[k][j];
          if (adjacencyMatrix[i][j] > newDist) {
            adjacencyMatrix[i][j] = newDist;
            nextVertex[i][j] = nextVertex[i][k];
          }
        }
      }
    }
  }
}

pair<vector<string>, int> CampusGraph::findShortestPath(const string &start,
                                                        const string &end) {
  vector<string> path;
  int start_num, end_num;

  try {
    start_num = stoi(start);
  } catch (...) {
    return {path, -1};
  }

  try {
    end_num = stoi(end);
  } catch (...) {
    return {path, -1};
  }

  int startIdx = start_num - 1;
  int endIdx = end_num - 1;

  if (adjacencyMatrix[startIdx][endIdx] == numeric_limits<int>::max()) {
    return {path, -1};
  }

  int currentIdx = startIdx;
  path.push_back(vertices[startIdx]);

  while (currentIdx != endIdx) {
    currentIdx = nextVertex[currentIdx][endIdx];
    path.push_back(vertices[currentIdx]);
  }

  return {path, adjacencyMatrix[startIdx][endIdx]};
}

// 添加新的辅助方法用于DP
int CampusGraph::dpTSP(int pos, int visited, vector<vector<int> > &dp,
                       vector<vector<int> > &parent,
                       const vector<int> &validVertices) {
  if (visited == ((1 << validVertices.size()) - 1)) {
    return adjacencyMatrix[validVertices[pos]][validVertices[0]];
  }

  if (dp[pos][visited] != -1) {
    return dp[pos][visited];
  }

  int ans = numeric_limits<int>::max();
  for (int i = 0; i < validVertices.size(); i++) {
    if (!(visited & (1 << i)) &&
        adjacencyMatrix[validVertices[pos]][validVertices[i]] !=
            numeric_limits<int>::max()) {
      int newAns = adjacencyMatrix[validVertices[pos]][validVertices[i]] +
                   dpTSP(i, visited | (1 << i), dp, parent, validVertices);
      if (newAns < ans) {
        ans = newAns;
        parent[pos][visited] = i;
      }
    }
  }

  return dp[pos][visited] = ans;
}

bool CampusGraph::isEulerian(const vector<int>& validVertices) {
    // 只检查有效顶点的度数
    for (int i : validVertices) {
        int degree = 0;
        for (int j : validVertices) {
            if (adjacencyMatrix[i][j] != numeric_limits<int>::max()) {
                degree++;
            }
        }
        if (degree % 2 != 0) {
            cout << "图中存在度数为奇数的顶点，无法形成欧拉回路！" << endl;
            return false;
        }
    }
    return true;
}

vector<string> CampusGraph::findIsolatedVertices(const string &entrance) {
  vector<string> isolatedVertices;
  int startIdx = vertexIndex[entrance];

  // 直接使用Floyd算法的结果来判断连通性
  for (int i = 0; i < numVertices; i++) {
    if (adjacencyMatrix[startIdx][i] == numeric_limits<int>::max()) {
      isolatedVertices.push_back(vertices[i]);
    }
  }

  return isolatedVertices;
}

vector<pair<vector<string>, int> >
CampusGraph::findTourPaths(const string &entrance, int maxPaths) {
  vector<pair<vector<string>, int> > allPaths;

  // 检查与起点不连通的点
  vector<string> isolatedVertices = findIsolatedVertices(entrance);
  if (!isolatedVertices.empty()) {
    cout << "\n警告：以下景点与起点 " << entrance << " 不连通：" << endl;
    for (const auto &vertex : isolatedVertices) {
      cout << "- " << vertex << endl;
    }
    cout << "这些景点将不会包含在回路计算中。" << endl;
  }

  // 创建不包含孤立点的新图
  vector<int> validVertices;
  for (int i = 0; i < numVertices; i++) {
    bool isIsolated = false;
    for (const auto &isolated : isolatedVertices) {
      if (vertices[i] == isolated) {
        isIsolated = true;
        break;
      }
    }
    if (!isIsolated) {
      validVertices.push_back(i);
    }
  }

  // 检查入口点是否是孤立点
  if (find(isolatedVertices.begin(), isolatedVertices.end(), entrance) !=
      isolatedVertices.end()) {
    cout << "错误：指定的入口点是孤立点，无法形成回路！" << endl;
    return allPaths;
  }

  int startIdx = vertexIndex[entrance];

  // 使用有效顶点检查是否可以形成欧拉回路
  if (!isEulerian(validVertices)) {
    return allPaths;
  }

  // 初始化DP表（只使用有效顶点）
  int validSize = validVertices.size();
  vector<vector<int> > dp(validSize, vector<int>(1 << validSize, -1));
  vector<vector<int> > parent(validSize, vector<int>(1 << validSize, -1));

  // 将startIdx映射到新图中的索引
  int newStartIdx = find(validVertices.begin(), validVertices.end(), startIdx) -
                    validVertices.begin();

  // 计算最短回路（使用有效顶点）
  int shortestDist =
      dpTSP(newStartIdx, 1 << newStartIdx, dp, parent, validVertices);

  // 重建路径（使用有效顶点）
  vector<string> path;
  int currentPos = newStartIdx;
  int currentMask = 1 << newStartIdx;
  path.push_back(entrance);

  while (currentMask != (1 << validSize) - 1) {
    int nextCity = parent[currentPos][currentMask];
    path.push_back(vertices[validVertices[nextCity]]);
    currentMask |= (1 << nextCity);
    currentPos = nextCity;
  }
  path.push_back(entrance);

  allPaths.push_back(make_pair(path, shortestDist));

  // 修改k-shortest paths算法以使用有效顶点
  typedef pair<int, vector<string> > PathPair;
  priority_queue<PathPair, vector<PathPair>, greater<PathPair> > pq;
  pq.push(make_pair(shortestDist, path));

  set<vector<string> > visited_paths;
  visited_paths.insert(path);

  while (!pq.empty() && allPaths.size() < maxPaths) {
    PathPair current = pq.top();
    int dist = current.first;
    vector<string> current_path = current.second;
    pq.pop();

    // 生成邻近路径
    for (int i = 0; i < current_path.size() - 2; i++) {
      for (int j = i + 2; j < current_path.size() - 1; j++) {
        vector<string> new_path = current_path;
        reverse(new_path.begin() + i + 1, new_path.begin() + j + 1);

        if (visited_paths.count(new_path))
          continue;

        // 计算新路径的距离（只考虑有效顶点间的边）
        int new_dist = 0;
        bool valid_path = true;
        for (size_t k = 0; k < new_path.size() - 1; k++) {
          int from = vertexIndex[new_path[k]];
          int to = vertexIndex[new_path[k + 1]];
          if (adjacencyMatrix[from][to] == numeric_limits<int>::max()) {
            valid_path = false;
            break;
          }
          new_dist += adjacencyMatrix[from][to];
        }

        if (valid_path) {
          pq.push(make_pair(new_dist, new_path));
          visited_paths.insert(new_path);
          allPaths.push_back(make_pair(new_path, new_dist));
        }
      }
    }
  }

  // 按距离排序
  sort(allPaths.begin(), allPaths.end(),
       [](const pair<vector<string>, int> &a,
          const pair<vector<string>, int> &b) { return a.second < b.second; });

  // 只保留前maxPaths条路径
  if (allPaths.size() > maxPaths) {
    allPaths.resize(maxPaths);
  }

  return allPaths;
}

void CampusGraph::showPath(const pair<vector<string>, int> &path) {
  for (size_t i = 0; i < path.first.size(); ++i) {
    cout << path.first[i];
    if (i < path.first.size() - 1) {
      cout << " →(走"
           << adjacencyMatrix[vertexIndex[path.first[i]]]
                             [vertexIndex[path.first[i + 1]]]
           << "米) ";
    }
  }
  cout << " | 总距离: " << path.second << "米。";
}

string CampusGraph::getVertexName(int index) {
  if (index >= 1 && index <= vertices.size()) {
    return vertices[index - 1];
  }
  return "";
}
